Nếu đã tìm hiểu về Thuật toán Dijkstra và Thuật toán Floyd-Warshall thì chúng ta biết rằng với đồ thị không có trọng số âm thì thuật toàn Dijkstra sẽ có tốc độ xử lý nhanh nhất O ( n 2 + m ) {\displaystyle O(n^{2}+m)}

còn Floyd-Warshal thì tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong thời gian O ( n 3 ) {\displaystyle O(n^{3})} . Mở rộng hơn nếu chúng ta áp dụng thuật toán Dijkstra (với Fibonacci Heap) n {\displaystyle n} lần, ta sẽ thu được thuật toán nhanh hơn hẳn O ( m + n log ⁡ n ) {\displaystyle O(m+n\log n)}

Vấn đề đặt ra là có tồn tại hay không thuật toán O ( m + n log ⁡ n ) {\displaystyle O(m+n\log n)} tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng, có trọng số âm và không có chu trình âm?

Thuật toán Johnson được tạo ra để giải quyết vấn đề này.